package com.itheima.datastructure.linkedlist;

import java.util.Stack;

/**
 * 反转链表 例如 [1,2,3,4,5] ==> [5,4,3,2,1]
 */
public class E01Leetcode206 {
    /**
     * 创建一个新链表 n1,从旧链表依次拿到每个节点，创建新节点添加到新链表头部
     *
     * @param o1
     * @return
     */
    public ListNode reverseList1(ListNode o1) {
        ListNode newHead = null; //新链表的头节点
        ListNode temp = o1;
        while (temp != null) {
            //创建一个新的节点，新节点的next指向新链表的头节点
            ListNode newNode = new ListNode(temp.val, newHead);
            //更新新链表头节点
            newHead = newNode;
            //移动到下一个节点
            temp = temp.next;
        }
        return newHead;
    }

    /**
     * 从旧链表依次取出节点，添加到新链表头部
     *
     * @param head 旧链表的头节点
     * @return 新链表的头节点
     * @return
     */
    public ListNode reverseList2(ListNode head) {
        //旧链表
        List list1 = new List(head);
        //新链表
        List list2 = new List(null);
        while (true) {
            //从旧链表移除第一个节点
            ListNode first = list1.removeFirst();
            if (first == null) {
                break;
            }
            //添加到新链表头部
            list2.addFirst(first);
        }
        return list2.head;
    }

    static class List {
        ListNode head;

        public List(ListNode head) {
            this.head = head;
        }

        public void addFirst(ListNode first) {
            first.next = head;
            head = first;
        }

        public ListNode removeFirst() {
            ListNode first = head;
            if (first != null) {
                head = first.next;
            }
            return first;
        }
    }

    /**
     * 递归：单项链表没有prev指针，利用了递归的特征【记住了】链表倒过来的顺序
     *
     * @param cur
     * @return
     */
    public ListNode reverseList3(ListNode cur) {
        if (cur == null || cur.next == null) {
            return cur; // 最后节点
        }

        ListNode last = reverseList3(cur.next);
        //----- '归'的过程图示1：
        //例：cur=4[4->5]                 --> 此处让 5->4  4->null 得到了 5->4->null
        //例：cur=3[3->5->4]              --> 此处让 4->3  3->null 得到了 5->4->3->null
        //例：cur=2[2->3->5->4]           --> 此处让 4->3->2  3->null 得到了 5->4->3->2->null
        //例：cur=1[1->2->3->5->4]        --> 此处让 4->3->2->1  2->null 得到了 5->4->3->2->1->null

        //----- '归'的过程图示2：
        // cur=4时,5->4, 4->null :   | 4 | 5 | null  -> | 5 | 4 | null
        // cur=3时,4->3 ,3->null :   | 3 | 5 | 4 | null -> | 5 | 4 | 3 | null
        // cur=2时,3->2, 2->null :   | 2 | 3 | 5 | 4 | null -> | 5 | 4 | 3 | 2 | null
        // cur=1时,2->1, 1->null :   | 1 | 2 | 3 | 5 | 4 | null -> | 5 | 4 | 3 | 2 | 1 | null

        cur.next.next = cur;

        cur.next = null;
        //返回最后的节点
        return last;
    }


    /**
     * 不断的从旧链表取出第二个节点，然后将取出的节点插入到新链表的头部 （用一个链表模拟了两个链表）
     *
     * @param o1 旧链表的头节点
     * @return 新链表的头节点
     * @return
     */
    //
    public ListNode reverseList4(ListNode o1) {
        // 1. 空链表  2. 一个元素
        if (o1 == null || o1.next == null) {
            return o1;
        }
        //o1-旧链表的头部
        //o2-旧链表的第二个节点
        //n1-新链表的头部指针
        ListNode o2 = o1.next;
        ListNode n1 = o1;
        while (o2 != null) {
            o1.next = o2.next;  // 2. 取出旧链表的第二个节点：旧链表的头节点的next指向 旧链表的第二节点的next
            o2.next = n1;       // 3. 被取出的节点的next指向新链表的头部
            n1 = o2;            // 4. n1变为新链表的头节点，（因为步骤3导致o2成为了新头）
            o2 = o1.next;       // 5. 旧链表移动到下一个节点
        }
        return n1;
    }

    /**
     * 方法2的面向过程版本：从旧链表依次取出节点，添加到新链表头部
     *
     * @param o1
     * @return
     */
    public ListNode reverseList5(ListNode o1) {
        if (o1 == null || o1.next == null) {
            return o1;
        }
        //o1-旧链表的头部
        //o2-旧链表的第二个节点
        //n1-新链表的头部指针
        ListNode n1 = null;
        while (o1 != null) {
            //记录下一个节点
            ListNode o2 = o1.next; // 2.
            o1.next = n1; // 3.
            n1 = o1;      // 4.
            o1 = o2;      // 4.o2成为旧链表节点的头节点
        }
        return n1;
    }


    /**
     * 利用栈结构
     *
     * @param o1
     * @return
     */
    public ListNode reverseList6(ListNode o1) {
        //向栈里面放节点
        Stack<ListNode> stack = new Stack<>();
        ListNode first = o1;
        while (first != null) {
            stack.push(first);
            first = first.next;
        }

        //头节点
        ListNode head = stack.pop();
        //前一节点
        ListNode pre = head;
        while (!stack.isEmpty()) {
            //弹出的节点
            ListNode pop = stack.pop();
            //前一节点的next指向弹出的节点
            pre.next = pop;
            //弹出节点为前一节
            pre = pop;
            //弹出的节点的next指向null
            pop.next = null;
        }
        return head;
    }

    public static void main(String[] args) {
        ListNode o5 = new ListNode(5, null);
        ListNode o4 = new ListNode(4, o5);
        ListNode o3 = new ListNode(3, o4);
        ListNode o2 = new ListNode(2, o3);
        ListNode o1 = new ListNode(1, o2);
        System.out.println(o1);
        ListNode n1 = new E01Leetcode206().reverseList3(o1);
        System.out.println(n1);
    }

}
